package sort;

public class Sort {
    //冒泡排序
    public int[] bubbleSort(int[] array) {
        int temp;
        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    //选择排序
    public int[] selectSort(int[] array) {
        int minValue;
        int index;
        for (int i = 0; i < array.length; i++) {
            int j;
            minValue = array[i];
            index = i;
            for (j = i + 1; j < array.length; j++) {
                if (minValue > array[j]) {
                    minValue = array[j];
                    index = j;
                }
            }
            minValue = array[index];
            array[index] = array[i];
            array[i] = minValue;

        }
        return array;
    }

    //插入排序
    public int[] insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j;
            for (j = i; j > 0 && array[j - 1] > temp; j--) {
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
        return array;
    }

    //快速排序
    public int[] quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
        return array;
    }

    public void quickSort(int[] array, int start, int end) {
        if (start < end) {
            int index = quickSortCore(array, start, end);
            quickSort(array, start, index - 1);
            quickSort(array, index + 1, end);
        }
    }

    public int quickSortCore(int[] array, int start, int end) {
        int pivot = array[start];
        int indexSmall = start + 1;
        int indexLarge = end;
        //将数组分成比主元大 和小 的两部分
        while (indexSmall < indexLarge) {
            //左侧小于右侧下标 并且 比主元小，左侧下标右移
            while (indexSmall <= indexLarge && array[indexSmall] <= pivot)
                indexSmall++;
            //左侧小于右侧下标 并且 比主元大，右侧下标左移
            while (indexSmall <= indexLarge && array[indexLarge] > pivot)
                indexLarge--;
            if (indexLarge > indexSmall) {
                int temp = array[indexSmall];
                array[indexSmall] = array[indexLarge];
                array[indexLarge] = temp;
            }
        }
        //交换主元到当前表示右侧的下标
        if (array[indexLarge] < pivot) {
            array[start] = array[indexLarge];
            array[indexLarge] = pivot;
            return indexLarge;
        } else return start;
    }

    //归并排序
    public int[] mergeSort(int[] array) {
        split(array);
        return array;

    }

    public void split(int[] array) {
        //等于1就返回
        if (array.length > 1) {
            int[] firstArray = new int[array.length / 2];
            int[] secondArray = new int[array.length - array.length / 2];
            System.arraycopy(array, 0, firstArray, 0, array.length / 2);
            System.arraycopy(array, array.length / 2, secondArray, 0, array.length - array.length / 2);
            //递归拆分
            split(firstArray);
            split(secondArray);
            //合并并复制回原数组
            int[] tempArray = merge(firstArray, secondArray);
            System.arraycopy(tempArray, 0, array, 0, tempArray.length);
        }
    }

    //合并
    private int[] merge(int[] firstArray, int[] secondArray) {
        int[] tempArray = new int[firstArray.length + secondArray.length];
        int firstArrayIndex = 0;
        int secondArrayIndex = 0;
        int temptArrayIndex = 0;
        while (firstArrayIndex < firstArray.length && secondArrayIndex < secondArray.length) {
            tempArray[temptArrayIndex++] = firstArray[firstArrayIndex] < secondArray[secondArrayIndex] ? firstArray[firstArrayIndex++] : secondArray[secondArrayIndex++];
        }
        //剩余未并入temp数组的元素并入
        while (firstArrayIndex < firstArray.length)
            tempArray[temptArrayIndex++] = firstArray[firstArrayIndex++];
        while (secondArrayIndex < secondArray.length)
            tempArray[temptArrayIndex++] = secondArray[secondArrayIndex++];
        return tempArray;
    }

    //堆排序
    public int[] heapSort(int[] array) {
        int len = array.length - 1;
        //构建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapAdjustment(array,i,len);
        }
        //调整堆结构+交换堆顶元素与末尾元素
        for(int j=len;j>0;j--){
            //将堆顶元素与末尾元素进行交换
            array[0] = array[0]+array[j];
            array[j] = array[0]-array[j];
            array[0] = array[0]-array[j];
            heapAdjustment(array,0,j);//重新对堆进行调整
        }
        return array;
    }
    //将数组结构调整为堆的结构
    private void heapAdjustment(int[] array,int index,int len){
        int temp = array[index];//先取出当前元素i
        for(int k = 2*index+1;k<len;k=k*2+1){
            if(k+1<len && array[k]<array[k+1])//判断右子节点是否大于左节点，大于则用右子节点与父节点比较
                k++;
            if(array[k]>temp){
                array[index] = array[k];
                index = k;
            }
            else break;//不需要调整
        }
        array[index] = temp;//最终交换
    }
}